1630B - Range and Partition - CodeForces Solution

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <math.h>

#define MAX 200010
#define MM 1000000001
#define ll long long

using namespace std;

int Modul(int x){return x>=0?x: -x;}

int a[MAX], a2[MAX], n, k, esqs[MAX], dirs[MAX];
bool percorrer(int x, int y){
    
    //cout << "x=" << x << " y=" << y << endl;
    int gp=0, cont=0, tam;
    tam=dirs[y]-esqs[x]+1;
    //cout << dirs[y] << " " << esqs[x] << endl;
    gp=tam-(n-tam);
    //cout << "gp=" << gp << endl;
    if(gp>=k) return true;
    return false;

}

bool flagG;
int meio, esqG, dirG, resEsq, resDir;

void buscaBinDir(int esq, int ini, int fim){

    if(ini>fim) return;

    int med;
    med=(ini+fim)/2;
    if(percorrer(a2[esq], a2[med])){
        flagG=true;
        //cout << "esqG=" << esq << " dirG=" << dirG << endl;
        dirG=med;
        buscaBinDir(esq, ini, med-1);
    }else{
        buscaBinDir(esq, med+1, fim);
    }

}

int main(){

    ios_base::sync_with_stdio(0);

    int test;
    cin >> test;

    vector <int> gps[MAX];
    string str;
    for(int tt=1;tt<=test;tt++){

        cin >> n >> k;
        //if(tt==2337)str=str+"("+to_string(n)+","+to_string(k)+")";
        for(int i=0;i<n;i++){
            cin >> a[i];
            a2[i]=a[i];
            gps[i].clear();
            //if(tt==2337)str=str+"|"+to_string(a[i]);
        }
        //if(tt==2337)cout << str << endl;
        gps[n].clear();
        sort(a2, &a2[n]);
        
        esqs[a2[0]]=0;
        for(int i=0;i<n-1;i++){
            if(a2[i]!=a2[i+1]){
                dirs[a2[i]]=i; esqs[a2[i+1]]=i+1;
            }
        }
        dirs[a2[n-1]]=n-1;

        resDir=MM; resEsq=-1;
        meio=(n-1)/2;

        for(int ini=0;ini<=meio;ini++){
            flagG=false;
            buscaBinDir(ini, meio, n-1);
            esqG=ini;
            if(flagG && (a2[dirG]-a2[esqG]<resDir-resEsq)){
                resEsq=a2[esqG]; resDir=a2[dirG];
            }
        }

        int cont=0, gp=0, ult=0;
        bool flag=true;
        for(int i=0;i<n;i++){
            if(flag){
                gps[ult].push_back(i+1);
                flag=false;
            }
            if(gp==k-1){
                gps[ult].push_back(n);
                ult++;
                break;
            }
            if(resEsq<=a[i] && a[i]<=resDir){
                cont++;
            }else{
                cont--;
            }
            
            if(cont==1){
                gps[ult].push_back(i+1);
                gp++;
                cont=0;
                ult++;
                flag=true;
            }
        }

        cout << resEsq << " " << resDir << endl;
        for(int i=0;i<ult;i++){
            for(int i2=0;i2<gps[i].size();i2++){
                cout << gps[i][i2] << " ";
            }cout << endl;
        }

    }

}